#ifndef _GRAPH_H_
#define _GRAPH_H_

#include <iostream>
#include <string>
#include <vector>
#include <list>
#define NUM_TOL 1e-10
using Weight = double;
using Index = int;
using Vertex = std::string;
using namespace std;

struct Edge
{
    Vertex *StartVertex;
    Vertex *EndVertex;
    Weight weight;
    Edge(Vertex *_start, Vertex *_end, Weight _w) : StartVertex(_start), EndVertex(_end), weight(_w){};
    string print() const
    {
        return "(" + *StartVertex + "," + *EndVertex + "," + to_string(weight) + ")";
    };
};

enum GraphStorageMode
{
    AdjList,
    AdjMatrix
};

GraphStorageMode AutoMode(int NumVertexes,int NumEdges)
{
    if(NumEdges > NumVertexes*NumVertexes/4.0)
        return GraphStorageMode::AdjMatrix;
    else
        return GraphStorageMode::AdjList;
}

template <GraphStorageMode M>
class Graph;

template <>
class Graph<GraphStorageMode::AdjMatrix>
{
private:
    vector<Vertex> Vertexes;
    vector<vector<Weight>> AdjMatrix;

public:
    Graph(const vector<Vertex> &_vertexes = {}, const vector<Edge> &_edges = {}) : Vertexes{_vertexes}
    {
        AdjMatrix.resize(Vertexes.size());
        for(size_t i=0; i< AdjMatrix.size(); i++)
            AdjMatrix[i].resize(AdjMatrix.size());
        for (auto _edge : _edges)
            AddEdge(_edge);
    }

    void AddVertex(const Vertex &_vertex)
    {
        Vertexes.push_back(_vertex);
        AdjMatrix.resize(AdjMatrix.size() + 1);
        for (size_t i = 0; i < AdjMatrix.size(); i++)
            AdjMatrix[i].resize(AdjMatrix.size() + 1);
    };

    void AddEdge(const Edge &_edge)
    {
        const auto Vbegin = Vertexes.begin();
        const auto Vend = Vertexes.end();
        for (auto it1 = Vbegin; it1 != Vend; it1++)
        {
            if (*it1 == *(_edge.StartVertex))
            {
                for (auto it2 = Vbegin; it2 != Vend; it2++)
                    if (*it2 == *(_edge.EndVertex))
                    {
                        AdjMatrix[distance(Vbegin, it1)][distance(Vbegin, it2)] = _edge.weight;
                        return;
                    }
            }
        }
        cout << "Vertexes in graph mismatch Edge " << _edge.print() << "\n";
        exit(-1);
    }

    void listVertexes() const
    {
        for (size_t i = 0; i < Vertexes.size(); i++)
            cout << i << ": " << Vertexes[i] << "\n";
    };

    void listEdges() const
    {
        for (size_t i = 0; i < Vertexes.size(); i++)
        {
            for (size_t j = 0; j < Vertexes.size(); j++)
            {
                if (abs(AdjMatrix[i][j]) > NUM_TOL)
                    cout << "(" << Vertexes[i] << "," << Vertexes[j] << "," << AdjMatrix[i][j] << ")\n";
            }
        }
    };
};

template <>
class Graph<GraphStorageMode::AdjList>
{
private:
    vector<Vertex> Vertexes;
    vector<list<pair<Index, Weight>>> AdjList;

public:
    Graph(const vector<Vertex> &_vertexes = {}, const vector<Edge> &_edges = {}) : Vertexes{_vertexes}
    {
        AdjList.resize(Vertexes.size());
        for (auto _edge : _edges)
            AddEdge(_edge);
    }

    void AddVertex(const Vertex &_vertex)
    {
        Vertexes.push_back(_vertex);
    };

    void AddEdge(const Edge &_edge)
    {
        const auto Vbegin = Vertexes.begin();
        const auto Vend = Vertexes.end();
        for (auto it1 = Vbegin; it1 < Vend; it1++)
        {
            if (*it1 == *(_edge.StartVertex))
            {
                for (auto it2 = Vbegin; it2 < Vend; it2++)
                    if (*it2 == *(_edge.EndVertex))
                    {
                        AdjList[distance(Vbegin, it1)].push_back(make_pair(distance(Vbegin, it2), _edge.weight));
                        return;
                    }
            }
        }
        cout << "Vertexes in graph mismatch Edge " << _edge.print() << "\n";
        exit(-1);
    }

    void listVertexes() const
    {
        for (size_t i = 0; i < Vertexes.size(); i++)
            cout << i << ": " << Vertexes[i] << "\n";
    };

    void listEdges() const
    {
        for (size_t i = 0; i < Vertexes.size(); i++)
        {
            for (auto it2 = AdjList[i].begin(); it2 != AdjList[i].end(); it2++)
                cout << "(" << Vertexes[i] << "," << Vertexes[(*it2).first] << "," << ((*it2).second) << ")\n";
        }
    };
};

#endif
